package com.cty.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/*
 *
 *
 * 马踏棋盘（骑士周游问题）
 *
 * */
public class horseChessBoard {
    private static int X;
    private static int Y;
    private static boolean[] isVisited;
    private static boolean finish;

    public static void main(String[] args) {
        X = 8;
        Y = 8;
        int[][] chessBoard = new int[X][Y];
        isVisited = new boolean[X*Y];
        System.out.println("开始执行~~");
        trip(chessBoard, 0, 0, 1);
        for (int i = 0; i < chessBoard.length; i++) {
            for (int j = 0;j < chessBoard[i].length;j++) {
                System.out.print(chessBoard[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public static void trip(int[][] chessBoard, int row, int column, int step) {
        chessBoard[row][column] = step;
        ArrayList<Point> ps = getPoints(new Point(column, row));
        sort(ps);
        isVisited[row * X + column] = true;
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);
            if (!isVisited[p.y * X + p.x]) {
                trip(chessBoard, p.y, p.x, step + 1);
            }
        }
        if (step < (X * Y) && !finish) {
            chessBoard[row][column] = 0;
            isVisited[row * X+ column] = false;
        } else {
            finish = true;
        }
    }


    public static ArrayList<Point> getPoints(Point curPoint) {
        ArrayList<Point> ps = new ArrayList<>();
        Point p1 = new Point();
        //加入5点
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //加入4点
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //加入6点
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //加入7点
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //加入0点
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //加入1点
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //加入2点
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //加入3点
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }
    public static  void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                int count1 = getPoints(o1).size();
                int count2 = getPoints(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }
}
